package com.cheng.learn.sort;

/**
 * @description: 希尔排序算法，渐进增加步长
 * @author: ChengHaiZhu
 * @create: 2021-03-20 10:11
 **/
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 , 23};
        shellSort(arr);
        System.out.println("排序后:");
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    /**
     * 希尔排序，先根据总长度的一半来排序，再迭代一半再来排序，知道步长为一
     * @param arr
     */
    public static void shellSort(int[] arr){
        int n = arr.length;
        for(int gap = n/2; gap > 0;gap /= 2) {
            for(int i = gap;i < n;i++) {
                // 因为需要判断 arr[j]和 arr[j - gap]关系，所以必须 要求 j > gap
                for(int j = i;j >= gap;j -= gap){
                    if(arr[j] < arr[j - gap]){
                        int temp = arr[j];
                        arr[j] = arr[j - gap];
                        arr[j - gap] = temp;
                    }
                }
            }
        }
    }
}
